package algorithms.leaning.class18;

import common.util.MyUtil;

/**
 * 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
 * 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
 * 如果机器人来到1位置，那么下一步只能往右来到2位置；
 * 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
 * 如果机器人来到中间位置，那么下一步可以往左走或者往右走；
 * 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
 * 给定四个参数 N、M、K、P，返回方法数。
 *
 * @author guichang
 * @date 2021/6/17
 */

@SuppressWarnings("all")
public class Code1_动态规划_机器人走路 {

    public static void main(String[] args) {
        MyUtil.print(ways(11, 6, 8, 10));
        MyUtil.print(waysDp(11, 6, 8, 10));
    }

    public static int ways(int N, int M, int P, int K) {
        if (N < 2 || M < 1 || M > N || P < 1 || P > N || K < 0) {
            return 0;
        }
        return process(N, P, M, K);
    }

    /**
     * 从curr到P走rest步有多少种方法
     *
     * @param N    范围
     * @param P    目标位置
     * @param index 当前位置
     * @param rest 还剩的步数
     * @return 方法数
     */
    private static int process(int N, int P, int index, int rest) {
        // 剩余步数为0的话，如果到了目标位置就记一种，否则不计
        if (rest == 0) {
            return index == P ? 1 : 0;
        }
        int ways = 0;
        // 在初始位置只能往右走
        if (index == 1) {
            ways = process(N, P, index + 1, rest - 1);
        }
        // 在终止位置只能往左走
        else if (index == N) {
            ways = process(N, P, index - 1, rest - 1);
        }
        // 在中间位置可往两边走
        else {
            int left = process(N, P, index - 1, rest - 1);
            int right = process(N, P, index + 1, rest - 1);
            ways = left + right;
        }
        return ways;
    }

    public static int waysDp(int N, int M, int P, int K) {
        if (N < 2 || M < 1 || M > N || P < 1 || P > N || K < 0) {
            return 0;
        }
        int[][] dp = new int[N + 1][K + 1];
        dp[P][0] = 1;
        for (int rest = 1; rest <= K; rest++) {
            // 第1行单独处理
            dp[1][rest] = dp[2][rest - 1];
            // 普遍位置
            for (int curr = 2; curr < N; curr++) {
                dp[curr][rest] = dp[curr - 1][rest - 1] + dp[curr + 1][rest - 1];
            }
            // 第N行单独处理
            dp[N][rest] = dp[N - 1][rest - 1];
        }
        return dp[M][K];
    }


}